//
// Created by Administrator on 2021/4/14.
//
/*给定一个 N 叉树，返回其节点值的 后序遍历 。

N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。


进阶：

递归法很简单，你可以使用迭代法完成此题吗?

示例 1：



输入：root = [1,null,3,2,4,null,5,6]
输出：[5,6,3,2,4,1]
示例 2：


输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]

提示：

N 叉树的高度小于或等于 1000
节点总数在范围 [0,10^4] 内

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

#include <vector>
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

// Definition for a Node.
class Node {
public:
    int val = 0;
    vector<Node *> children;

    Node() = default;

    explicit Node(int _val) : val(_val) {};

    Node(int _val, vector<Node *> _children) {
        val = _val;
        children = std::move(_children);
    }
};

/**
 * 在后序遍历中，我们会先遍历一个节点的所有子节点，再遍历这个节点本身。
 * 例如当前的节点为 u，它的子节点为 v1, v2, v3 时，那么后序遍历的结果为
 * [children of v1], v1, [children of v2], v2, [children of v3], v3, u，
 * 其中 [children of vk] 表示以 vk 为根节点的子树的后序遍历结果（不包括 vk 本身）。
 * 我们将这个结果反转，可以得到 u, v3, [children of v3]', v2, [children of v2]', v1, [children of v1]'，
 * 其中 [a]' 表示 [a] 的反转。此时我们发现，结果和前序遍历非常类似，只
 * 不过前序遍历中对子节点的遍历顺序是 v1, v2, v3，而这里是 v3, v2, v1。

因此我们可以使用和 N叉树的前序遍历 相同的方法，使用一个栈来得到后序遍历。
 我们首先把根节点入栈。当每次我们从栈顶取出一个节点 u 时，就把 u 的所有子节点顺序推入栈中。
 例如 u 的子节点从左到右为 v1, v2, v3，那么推入栈的顺序应当为 v1, v2, v3，
 这样就保证了下一个遍历到的节点（即 u 的第一个子节点 v3）出现在栈顶的位置。
 在遍历结束之后，我们把遍历结果反转，就可以得到后序遍历。
**/
class Solution {
public:
    vector<int> postorder(Node *root) {
        vector<int> ret;
        dfs(root, ret);
        return ret;
    }

    void dfs(Node *root, vector<int> &v) {
        if (!root) return;
        for (auto &x:root->children) {
            dfs(x, v);
        }
        v.push_back(root->val);
    }

    vector<int> postorderRecursive(Node *root) {
        vector<int> ret;
        if (!root) return ret;
        stack<Node *> stk;
        stk.push(root);
        while (!stk.empty()) {
            Node *temp = stk.top();
            stk.pop();
            ret.push_back(temp->val);
            for (auto &i : temp->children) {
                // 顺序放入
                stk.push(i);
            }
        }
        reverse(ret.begin(), ret.end()); //倒序
        return ret;
    }
};


int main() {
    auto t6 = Node(6);
    auto t5 = Node(5);
    auto t4 = Node(4);
    auto t3 = Node(2);
    auto t2 = Node(3, vector<Node *>{&t5, &t6});
    auto t1 = Node(1, vector<Node *>{&t2, &t3, &t4});
    Solution sol;
    vector<int> v = sol.postorderRecursive(&t1);
    for (const auto &x:v) cout << x;
    return 0;
}
